package com.LeeCode;

/**
 * 打家劫舍 III
 */

public class Code337 {
    public static void main(String[] args) {
        Integer[] arr = {4, 1, null, 2, null, 3};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code337().rob(root));
    }

    public int rob(TreeNode root) {
        Result ans = dfs(root);
        return Math.max(ans.rob, ans.noRob);
    }

    private Result dfs(TreeNode root) {
        if (root == null)
            return new Result(0, 0);
        if (root.left == null && root.right == null)
            return new Result(root.val, 0);
        Result left = dfs(root.left);
        Result right = dfs(root.right);
        int rob = root.val + left.noRob + right.noRob;
        int noRob = Math.max(left.rob, left.noRob) + Math.max(right.rob, right.noRob);
        return new Result(rob, noRob);
    }

    class Result {
        int rob, noRob;

        public Result(int rob, int noRob) {
            this.rob = rob;
            this.noRob = noRob;
        }
    }

}
